Walaupun ekonomi Indonesia pulih sebahagiannya daripada krisis pada 1997, kadar pengganguran dan kemiskinan kekal di paras yang tinggi, dan terdapat kekesalan terhadap perlantikan Megawati sebagai presiden. Perlembagaan Indonesia telah diubah untuk membenarkan perlantikan langsung Presiden, dan penggal Megawati akan tamat pada 2004.

Pada Julai 2004, Megawati bertanding untuk penggal kedua. Beliau berterusan ketinggalan dalam pungutan pendapat umum, sebahagiannya disebabkan kecenderungan untuk calon lelaki di kalangan pengundi Muslim, dan sebahagiannya disebabkan prestasi sederhananya ketika berkuasa. Beliau akhirnya tewas dan digantikan oleh Susilo Bambang Yudhoyono.